
/**
 * Simple doubly linked list implementation.
 * It is modified based on Linux Kernel (include/linux/list.h)
 *
 * @file
 * @author daoyuan (2009-12-30)
 *
 * @addtogroup LIB_LINKLIST Link list operations
 * @ingroup LIB
 * @{
 */

#ifndef __LIST_H
#define __LIST_H

#include <data_type_def.h>

typedef struct list_head
{
	struct list_head *next;
	struct list_head *prev;
}list_head_t;


/**
 * list_init - initialize list head
 * @param  ptr: list head to be initialized
 *
 */
static inline void list_init(list_head_t * ptr)
{
	(ptr)->next = (ptr);
	(ptr)->prev = (ptr);
}

/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_add(list_head_t *new_entry,
			      list_head_t *prev,
			      list_head_t *next)
{
	next->prev = new_entry;
	new_entry->next = next;
	new_entry->prev = prev;
	prev->next = new_entry;
}

/**
 * list_append - add a new entry
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 *
 * @param  new_entry: new entry to be added
 * @param  head: list head to add it before
 *
 */
static inline void list_append(list_head_t *new_entry, list_head_t *head)
{
	__list_add(new_entry, head->prev, head);
}

/**
 * list_add - add a new entry
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 *
 * @param  new_entry: new entry to be added
 * @param  head: list head to add it after
 */
static inline void list_add(list_head_t *new_entry, list_head_t *head)
{
	__list_add(new_entry, head, (head)->next);
}

/**
 * list_insert - add a new entry
 * Insert a new entry after the specified position.
 * This is good for more flexible inplementations which requires add a new entry at an arbitrary place in a list.
 *
 * @param  new_entry: new entry to be added
 * @param  pos: the position in a list to add after
 */
static inline void list_insert(list_head_t *new_entry, list_head_t *pos)
{
	__list_add(new_entry, (pos), (pos)->next);
}

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(list_head_t *prev, list_head_t *next)
{
	next->prev = prev;
	prev->next = next;
}

/**
 * list_del - deletes entry from list.
 * Note: list_empty on entry does not return true after this, the entry is in an undefined state.
 *
 * @param  entry: the element to be deleted from the list.
 */
static inline void list_del(list_head_t *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = (list_head_t *) NULL;
	entry->prev = (list_head_t *) NULL;
}

/**
 * list_empty - tests whether a list is empty
 *
 * @param  head: the list to test.
 *
 * @return  TRUE on list empty, FALSE on list not empty
 */
static inline bool_t list_empty(list_head_t *head)
{
	return (((head)->next == head) || (head->next == NULL));
}

/**
 * list_entry - get the struct for this entry
 *
 * @param  ptr:	the &list_head_t pointer.
 * @param  type:	the type of the struct this is embedded in.
 * @param  member:	the name of the list_struct within the struct.
 *
 * @return  pointer to the structure of the list entry.
 */
#define list_entry(ptr, type, member) \
        ((type *)((char *)(ptr)-(unsigned long)(&((type *)NULL)->member)))
#define list_buf_entry(ptr, type, member) \
		(ptr!=NULL)?((type *)((char *)(ptr)-(unsigned long)(&((type *)NULL)->member))):((type *)NULL)

/*
 * Delete and return a head entry
 *
 * Internal implementation
 */
static inline list_head_t *__list_decap(list_head_t *head)
{
	if (head == NULL){
		return NULL;
	}
	list_head_t *temp = (head)->next;
	__list_del(head, temp->next);
	temp->next = (list_head_t *) NULL;
	temp->prev = (list_head_t *) NULL;
	return temp;
}
	
/**
 * list_entry_decap - remove the head entry, and return the struct of head entry; return (void *)NULL if list empty
 *
 * @param  head:	the head for your list.
 * @param  type:	the type of the struct this is embedded in.
 * @param  member:	the name of the list_struct within the struct.
 *
 * @return  pointer to the structure of first list entry, NULL on list empty
 */
#define list_entry_decap(head, type, member) \
	((list_empty(head))?(type *)NULL:(list_entry(__list_decap(head), type, member)))\

/**
 * list_get_head	-	return the first entry in a list
 *
 * @param  head:	the head for your list.
 *
 * @return  pointer to first list entry, NULL on list empty
 */
static inline list_head_t * list_get_head(list_head_t *head)
{
	return ((list_empty(head))?(list_head_t *)NULL:((head)->next));
}

/**
 * list_entry_get_head - get the struct of head entry
 *
 * @param  head:	the head for your list.
 * @param  type:	the type of the struct this is embedded in.
 * @param  member:	the name of the list_struct within the struct.
 *
 * @return  pointer to the structure of first list entry, NULL on list empty
 */
#define list_entry_get_head(head, type, member) \
	((list_empty(head))?(type *)NULL:(list_entry((head)->next, type, member)))

/**
 * list_for_each	-	iterate over a list
 *
 * @param  pos:	the &list_head_t to use as a loop counter.
 * @param  head:	the head for your list.
 */
#define list_for_each(pos, head) \
	for ((pos) = (head)->next; (pos) != (head); \
		(pos) = (pos)->next)

/**
 * list_for_each_entry	-	iterate over list of given type
 *
 * @param  pos:	the type * to use as a loop counter.
 * @param  head:	the head for your list.
 * @param  type:	the type of the struct this is embedded in.
 * @param  member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry(pos, head, type, member)				\
	for ((pos) = list_entry((head)->next, type, member);	\
	     &(pos)->member != (head); 					\
	     (pos) = list_entry((pos)->member.next, type, member))
	
/**
 * list_del_head	-	delete the first entry in a list
 * Note: use list_entry_decap for delete and return the structure of entry
 *
 * @param  head:	the head for your list.
 */
static inline void list_del_head(list_head_t *head)
{
	list_del((head)->next);
}

/* -----------------------------hidden API, to be revealed when necessary-------------------------------*/

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	list_head_t name = LIST_HEAD_INIT(name)
	
#define INIT_LIST_HEAD(ptr) do { \
	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

/**
 * list_move - delete from one list and add as another's head
 *
 * @param  list: the entry to move
 * @param  head: the head that will precede our entry
 */
static inline void list_move(list_head_t *list, list_head_t *head)
{
	__list_del(list->prev, list->next);
	list_add(list, head);
}

/**
 * list_move_tail - delete from one list and add as another's tail
 *
 * @param  list: the entry to move
 * @param  head: the head that will follow our entry
 */
static inline void list_move_tail(list_head_t *list,
				  list_head_t *head)
{
	__list_del(list->prev, list->next);
	list_append(list, head);
}

/**
 * list_for_each_prev	-	iterate over a list backwards
 *
 * @param  pos:	the &list_head_t to use as a loop counter.
 * @param  head:	the head for your list.
 */
#define list_for_each_prev(pos, head) \
	for ((pos) = (head)->prev; (pos) != (head); \
		(pos) = (pos)->prev)
        	
/**
 * list_for_each_safe	-	iterate over a list safe against removal of list entry
 *
 * @param  pos:	the &list_head_t to use as a loop counter.
 * @param  n:		another &list_head_t to use as temporary storage
 * @param  head:	the head for your list.
 */
#define list_for_each_safe(pos, n, head) \
	for ((pos) = (head)->next, n = (pos)->next; (pos) != (head); \
		(pos) = n, n = (pos)->next)

/**
 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 *
 * @param  pos:	the type * to use as a loop counter.
 * @param  n:		another type * to use as temporary storage
 * @param  head:	the head for your list.
 * @param  type:	the type of the struct this is embedded in.
 * @param  member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry_safe(pos, n, head, type, member)			\
	for ((pos) = list_entry((head)->next, type, member),	\
		n = list_entry((pos)->member.next, type, member);	\
		&(pos)->member != (head); 					\
		(pos) = n, n = list_entry(n->member.next, type, member))

/*
 * Delete and return a tail entry
 *
 * Internal implementation
 */
static inline list_head_t *__list_curtail(list_head_t *head)
{
	list_head_t *temp = head->prev;
	__list_del(temp->prev, head);
	temp->next = (list_head_t *) NULL;
	temp->prev = (list_head_t *) NULL;
	return temp;
}

/**
 * list_entry_curtail - remove the tail entry, and return the struct of tail entry; return (void *)NULL if list empty
 *
 * @param  head:	the head for your list.
 * @param  type:	the type of the struct this is embedded in.
 * @param  member:	the name of the list_struct within the struct.
 *
 * @return  pointer to the structure of last list entry, NULL on list empty
 */
#define list_entry_curtail(head, type, member) \
	((list_empty(head))?(type *)NULL:(list_entry(__list_curtail(head), type, member)))

/**
 * list_count	-	count number of entries in the list
 *
 * @param  count:	a predefined int variable.
 * @param  head:	the head for your list.
 *
 * @return  count is the inexplicit return value
 */
#define list_count(head,count) \
	count=0;\
	for (list_head_t *pos = (head)->next; pos != (head); pos = pos->next)\
		{count++;}


inline bool_t list_push(list_head_t *list_head, list_head_t * list_2be_add)
{
	if (list_2be_add == NULL)
	{
		return FALSE;
	}
	
	list_2be_add->next = list_head->next;
	list_head->next = list_2be_add;
	
	return TRUE;
}

inline list_head_t *list_pop(list_head_t *list_head)
{
	if (list_head->next != NULL)
	{
		list_head_t *cursor = list_head->next;
		list_head->next = cursor->next;
		cursor->next = NULL;
		return cursor;
	}
	else
	{
		return NULL;
	}
}


/**
 * list_sorted_add	-	iterate over a sorted list, and add a new entry to a proper position
 *
 * @param  new_entry: new entry to be added
 * @param  head: list head
 * @param  type:	the type * to use as a loop counter.
 * @param  member:	the name of the list_struct within the struct.
 * @param  funcCompare:user defined compare function, the type must be like this- bool func(Node* A, Node* B), if A < B, return true, else return false
 */
#define list_sorted_add(new_entry,head,type,member,funcCompare,pos) \
do {\
	for ((pos) = (head)->next; (pos) != (head); (pos) = (pos)->next){\
		if (funcCompare(list_entry((new_entry), type, member),list_entry(pos, type, member))){\
			break;\
		}\
	}\
	if ((pos) != (head)){\
		__list_add((new_entry), (pos)->prev, (pos));\
	}else{\
		list_append((new_entry),(head));\
	}\
} while(0)

#endif
/**
 * @}
 */

